Graphs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace algorithms.graphs
{
// ----- Bipartite --------------------------------------------
//
// The class represents a data type for determining whether
// an UNDIRECTED graph is bipartite or whether it has
// an odd-length cycle.
//
// O(V + E)
//
// http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Bipartite.java.html
//
// Depends on:
// -- Graph (algorithms.graphs)
//
// DijkstraSP(Graph g, int s)
// int Dist(int v)
// bool HasPath(int v)
// IEnumerable<int> Path(int v)
// -------------------------------------------------------------------------
public class Bipartite
{
public bool IsBipartite { get; private set; }
bool[] color = null;
bool[] marked = null;
int[] edgeTo = null;
Stack<int> cycle = null;
public Bipartite(Graph g)
{
IsBipartite = true;
color = new bool[g.V];
marked = new bool[g.V];
edgeTo = new int[g.V];
for (int v = 0; v < g.V; v++)
if (!marked[v])
Dfs(g, v);
}
void Dfs(Graph g, int v)
{
marked[v] = true;
for (int i = 0; i < g.Deg(v); i++) {
int w = g.AdjV(v, i);
if (cycle != null) return;
if (!marked[w])
{
edgeTo[w] = v;
color[w] = !color[v];
Dfs(g, w);
}
else
if (color[w] == color[v])
{
IsBipartite = false;
cycle = new Stack<int>();
cycle.Push(w); // don't need this unless you want to include start vertex twice
for (int x = v; x != w; x = edgeTo[x]) cycle.Push(x);
cycle.Push(w);
}
}
}
public IEnumerable<int> OddCycle()
{
return cycle;
}
}
// -------------------------------------------------------------------------
}
using System.Collections.Generic;
namespace algorithms.graphs
{
// ----- Connected Components ----------------------------------------------
//
// http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/CC.java.html
//
// Depends on:
// -- Graph (algorithms.graphs)
//
// ConnectedComponents(Graph g)
// bool Connected(int u, int v)
// int Count
// int ID(int v)
// int Size(int id)
// -------------------------------------------------------------------------
public class ConnectedComponents
{
public int Count { get; private set; }
int[] id = null;
int[] size = null;
public ConnectedComponents(Graph g)
{
bool[] marked = new bool[g.V];
Count = 0;
id = new int[g.V];
size = new int[g.V];
Stack<int> stack = new Stack<int>();
for (int u = 0; u < g.V; u++)
if (!marked[u])
{
stack.Clear();
stack.Push(u);
while (stack.Count > 0)
{
int v = stack.Pop();
marked[v] = true;
id[v] = Count;
size[Count]++;
for (int i = 0; i < g.Deg(v); i++)
{
int v1 = g.AdjV(v, i);
if (!marked[v1]) stack.Push(v1);
}
}
Count++;
}
}
public int ID(int v) { return id[v]; }
public int Size(int id) { return size[id]; }
public bool Connected(int u, int v)
{
return id[u] == id[v];
}
}
// -------------------------------------------------------------------------
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using algorithms.structures;
namespace algorithms.graphs
{
// ----- Dijkstra Shortest Path --------------------------------------------
//
// http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/DijkstraSP.java.html
//
// Depends on:
// -- Graph (algorithms.graphs)
// -- IndexBinaryHeapPQ (algorithms.structures)
//
// DijkstraSP(Graph g, int s)
// int Dist(int v)
// bool HasPath(int v)
// IEnumerable<int> Path(int v)
// -------------------------------------------------------------------------
public class DijkstraSP
{
int[] dist = null;
int[] prev = null;
IndexBinaryHeapPQ<int> pq = null;
public DijkstraSP(Graph g, int s)
{
dist = new int[g.V];
prev = new int[g.V];
for (int i = 0; i < g.V; i++)
{
dist[i] = int.MaxValue;
prev[i] = -1;
}
dist[s] = 0;
pq = new IndexBinaryHeapPQ<int>(g.V);
pq.Insert(s, dist[s]);
while (pq.Count > 0)
{
int v = pq.ExtractMin();
for (int i = 0; i < g.Deg(v); i++) Relax(v, g.AdjV(v, i), g.AdjW(v, i));
}
}
public int Dist(int v)
{
return dist[v];
}
public bool HasPath(int v)
{
return dist[v] < int.MaxValue;
}
public IEnumerable<int> Path(int v)
{
if (!HasPath(v)) return null;
Stack<int> stack = new Stack<int>();
while (v != -1)
{
stack.Push(v);
v = prev[v];
}
return stack;
}
void Relax(int u, int v, int w)
{
if (dist[v] > dist[u] + w)
{
dist[v] = dist[u] + w;
prev[v] = u;
if (pq.Contains(v)) pq.Decrease(v, dist[v]);
else pq.Insert(v, dist[v]);
}
}
public static int[,] SP(Graph g)
{
int[,] sp = new int[g.V, g.V];
for (int v = 0; v < g.V; v++)
{
DijkstraSP dsp = new DijkstraSP(g, v);
for (int u = 0; u < g.V; u++) sp[v, u] = dsp.Dist(u);
}
return sp;
}
}
// -------------------------------------------------------------------------
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace algorithms.graphs
{
// ----- Graph -------------------------------------------------------------
//
// Graph(int v, IEnumerable<int[]> edges, bool directed = false)
// int AdjV(int v, int ix)
// int AdjW(int v, int ix)
// int Deg(int v)
// int[][] IncidenceMatrix()
// override string ToString()
// -------------------------------------------------------------------------
public class Graph
{
public int V { get; private set; }
// [][ v1, v2 ... ]
int[][] adj = null;
// [][ w1, w2 ... ]
int[][] wt = null;
// edges: [][u, v, w]
public Graph(int v, IEnumerable<int[]> edges, bool directed = false)
{
V = v;
adj = new int[V][];
wt = new int[V][];
int[][] e2a = edges.ToArray();
int[] deg = new int[V];
foreach (int[] e in e2a)
{
deg[e[0]]++;
if (!directed) deg[e[1]]++;
}
for (int i = 0; i < V; i++)
{
adj[i] = new int[deg[i]];
wt[i] = new int[deg[i]];
}
Array.Clear(deg, 0, V);
foreach (int[] e in e2a)
{
adj[e[0]][deg[e[0]]] = e[1];
wt[e[0]][deg[e[0]]] = e[2];
deg[e[0]]++;
if (!directed)
{
adj[e[1]][deg[e[1]]] = e[0];
wt[e[1]][deg[e[1]]] = e[2];
deg[e[1]]++;
}
}
}
public int AdjV(int v, int ix)
{
return adj[v][ix];
}
public int AdjW(int v, int ix)
{
return wt[v][ix];
}
public int Deg(int v)
{
return adj[v].Length;
}
public int[][] IncidenceMatrix()
{
int[][] mx = new int[V][];
for (int v = 0; v < V; v++) mx[v] = new int[V];
for (int v = 0; v < V; v++)
{
for (int i = 0; i < Deg(v); i++)
{
mx[v][AdjV(v, i)] = AdjW(v, i);
mx[AdjV(v, i)][v] = -AdjW(v, i);
}
}
return mx;
}
public int[] SortByPreorder(int root)
{
int[] stack = new int[V];
int nstack = 0;
int[] order = new int[V];
int norder = 0;
bool[] visited = new bool[V];
stack[nstack++] = root;
visited[root] = true;
while (nstack > 0)
{
int v = stack[--nstack];
order[norder++] = v;
for (int i = 0; i < Deg(v); i++)
{
int u = AdjV(v, i);
if (!visited[u])
{
visited[u] = true;
stack[nstack++] = u;
}
}
}
return order;
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
for (int v = 0; v < V; v++)
sb.AppendFormat("{0}:{1}", v, string.Join(",", Enumerable.Range(0, adj[v].Length).Select(p => string.Format("{0}[{1}]", adj[v][p], wt[v][p])).ToArray())).AppendLine();
return sb.ToString();
}
}
// -------------------------------------------------------------------------
}
using algorithms.structures;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace algorithms.graphs
{
// ----- Graph Generator ---------------------------------------------------
//
// provides methods for creating various graphs
//
// Depends on:
// -- Graph (algorithms.graphs)
// -- BinaryHeapPQ (algorithms.structures)
//
// GraphGenerator(int seed)
// Graph Simple(int V, int E, bool directed = false)
// Graph Simple(int V, double p, bool directed = false)
// Graph Bipartite(int V1, int V2, int E)
// Graph Bipartite(int V1, int V2, double p)
// Graph Path(int V, bool directed = false)
// Graph BinaryTree(int V)
// Graph Cycle(int V, bool directed = false)
// Graph EulerianPath(int V, int E, bool directed = false)
// Graph EulerianCycle(int V, int E, bool directed = false)
// Graph Wheel(int V, bool directed = false)
// Graph Star(int V, bool directed = false)
// Graph Regular(int V, int k, bool directed = false)
// Graph Tree(int V)
// -------------------------------------------------------------------------
public class GraphGenerator
{
Random random = null;
public GraphGenerator(int seed)
{
random = new Random(seed);
}
public Graph Simple(int V, int E, bool directed = false)
{
if (E < 0 || E > (long)V * (V - 1) / 2) return null;
HashSet<long> hs = new HashSet<long>();
List<int[]> edges = new List<int[]>();
while (edges.Count() < E)
{
int u = random.Next(V);
int v = random.Next(V);
if (u != v)
{
if (!directed && u > v) { int t = u; u = v; v = t; }
long key = (long)u * int.MaxValue + v;
if (!hs.Contains(key))
{
hs.Add(key);
edges.Add(new int[] { u, v, 1 });
}
}
}
Graph g = new Graph(V, edges, directed);
return g;
}
public Graph Simple(int V, double p, bool directed = false)
{
if (p < 0.0 || p > 1.0) return null;
List<int[]> edges = new List<int[]>();
for (int u = 0; u < V; u++)
for (int v = directed ? 0 : u + 1; v < V; v++)
if (u != v && random.NextDouble() < p) edges.Add(new int[] { u, v, 1 });
Graph g = new Graph(V, edges, directed);
return g;
}
void Shuffle<T>(T[] array)
{
int n = array.Length;
for (int i = 0; i < n; i++)
{
int r = i + (int)(random.NextDouble() * (n - i));
T t = array[r];
array[r] = array[i];
array[i] = t;
}
}
public Graph Bipartite(int V1, int V2, int E)
{
if (E < 0 || E > (long)V1 * V2) return null;
int[] vertices = new int[V1 + V2];
for (int i = 0; i < V1 + V2; i++) vertices[i] = i;
Shuffle(vertices);
HashSet<long> hs = new HashSet<long>();
List<int[]> edges = new List<int[]>();
while (edges.Count() < E)
{
int u = vertices[random.Next(V1)];
int v = vertices[V1 + random.Next(V2)];
long key = (long)u * int.MaxValue + v;
if (!hs.Contains(key))
{
hs.Add(key);
edges.Add(new int[] { u, v, 1 });
}
}
Graph g = new Graph(V1 + V2, edges, false);
return g;
}
public Graph Bipartite(int V1, int V2, double p)
{
if (p < 0.0 || p > 1.0) return null;
int[] vertices = new int[V1 + V2];
for (int i = 0; i < V1 + V2; i++) vertices[i] = i;
Shuffle(vertices);
List<int[]> edges = new List<int[]>();
for (int i = 0; i < V1; i++)
for (int j = 0; j < V2; j++)
if (random.NextDouble() < p)
edges.Add(new int[] { vertices[i], vertices[V1 + j], 1 });
Graph g = new Graph(V1 + V2, edges, false);
return g;
}
public Graph Path(int V, bool directed = false)
{
int[] vertices = new int[V];
for (int i = 0; i < V; i++) vertices[i] = i;
Shuffle(vertices);
List<int[]> edges = new List<int[]>();
for (int i = 0; i < V - 1; i++) edges.Add(new int[] { vertices[i], vertices[i + 1], 1 });
Graph g = new Graph(V, edges, directed);
return g;
}
public Graph BinaryTree(int V)
{
int[] vertices = new int[V];
for (int i = 0; i < V; i++) vertices[i] = i;
Shuffle(vertices);
List<int[]> edges = new List<int[]>();
for (int i = 1; i < V; i++) edges.Add(new int[] { vertices[i], vertices[(i - 1) / 2], 1 });
Graph g = new Graph(V, edges, false);
return g;
}
public Graph Cycle(int V, bool directed = false)
{
int[] vertices = new int[V];
for (int i = 0; i < V; i++) vertices[i] = i;
Shuffle(vertices);
List<int[]> edges = new List<int[]>();
for (int i = 0; i < V - 1; i++) edges.Add(new int[] { vertices[i], vertices[i + 1], 1 });
edges.Add(new int[] { vertices[V - 1], vertices[0], 1 });
Graph g = new Graph(V, edges, directed);
return g;
}
public Graph EulerianPath(int V, int E, bool directed = false)
{
if (E < 0 || V <= 0) return null;
int[] vertices = new int[E + 1];
for (int i = 0; i < E + 1; i++) vertices[i] = random.Next(V);
List<int[]> edges = new List<int[]>();
for (int i = 0; i < E; i++) edges.Add(new int[] { vertices[i], vertices[i + 1], 1 });
Graph g = new Graph(V, edges, directed);
return g;
}
public Graph EulerianCycle(int V, int E, bool directed = false)
{
if (E <= 0 || V <= 0) return null;
int[] vertices = new int[E];
for (int i = 0; i < E; i++) vertices[i] = random.Next(V);
List<int[]> edges = new List<int[]>();
for (int i = 0; i < E - 1; i++) edges.Add(new int[] { vertices[i], vertices[i + 1], 1 });
edges.Add(new int[] { vertices[E - 1], vertices[0], 1 });
Graph g = new Graph(V, edges, directed);
return g;
}
public Graph Wheel(int V, bool directed = false)
{
if (V <= 1) return null;
int[] vertices = new int[V];
for (int i = 0; i < V; i++) vertices[i] = i;
Shuffle(vertices);
List<int[]> edges = new List<int[]>();
for (int i = 1; i < V - 1; i++) edges.Add(new int[] { vertices[i], vertices[i + 1], 1 });
edges.Add(new int[] { vertices[V - 1], vertices[1], 1 });
for (int i = 1; i < V; i++) edges.Add(new int[] { vertices[0], vertices[i], 1 });
Graph g = new Graph(V, edges, directed);
return g;
}
public Graph Star(int V, bool directed = false)
{
if (V <= 0) return null;
int[] vertices = new int[V];
for (int i = 0; i < V; i++) vertices[i] = i;
Shuffle(vertices);
List<int[]> edges = new List<int[]>();
for (int i = 1; i < V; i++) edges.Add(new int[] { vertices[0], vertices[i], 1 });
Graph g = new Graph(V, edges, directed);
return g;
}
public Graph Regular(int V, int k, bool directed = false)
{
if (V * k % 2 != 0) return null;
int[] vertices = new int[V * k];
for (int v = 0; v < V; v++)
for (int j = 0; j < k; j++)
vertices[v + V * j] = v;
Shuffle(vertices);
List<int[]> edges = new List<int[]>();
for (int i = 0; i < V * k / 2; i++)
edges.Add(new int[] { vertices[2 * i], vertices[2 * i + 1], 1 });
Graph g = new Graph(V, edges, directed);
return g;
}
public Graph Tree(int V)
{
if (V == 1) return new Graph(V, new int[][] { });
int[] prufer = new int[V - 2];
for (int i = 0; i < V - 2; i++) prufer[i] = random.Next(V);
int[] degree = new int[V];
for (int v = 0; v < V; v++) degree[v] = 1;
for (int i = 0; i < V - 2; i++) degree[prufer[i]]++;
BinaryHeapPQ<int> pq = new BinaryHeapPQ<int>();
for (int v = 0; v < V; v++)
if (degree[v] == 1)
pq.Insert(v);
List<int[]> edges = new List<int[]>();
for (int i = 0; i < V - 2; i++)
{
int v = pq.ExtractMin();
edges.Add(new int[] { v, prufer[i], 1 });
degree[v]--;
degree[prufer[i]]--;
if (degree[prufer[i]] == 1) pq.Insert(prufer[i]);
}
edges.Add(new int[] { pq.ExtractMin(), pq.ExtractMin(), 1 });
Graph g = new Graph(V, edges, false);
return g;
}
}
// -------------------------------------------------------------------------
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using algorithms.structures;
namespace algorithms.graphs
{
// ----- Kruskal Minimum Spanning Tree (Forest) ----------------------------
//
// http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/KruskalMST.java.html
//
// Depends on:
// -- Graph (algorithms.graphs)
// -- BinaryHeapPQ (algorithms.structures)
// -- DisjointSets (algorithms.structures)
//
// KruskalMST(Graph g)
// IEnumerable<int[]> MST()
// -------------------------------------------------------------------------
public class KruskalMST
{
public class Edge: IComparable
{
public int U { get; set; }
public int V { get; set; }
public int W { get; set; }
public int CompareTo(object obj)
{
return W.CompareTo((obj as Edge).W);
}
}
List<Edge> mst = new List<Edge>();
public KruskalMST(Graph g)
{
BinaryHeapPQ<Edge> pq = new BinaryHeapPQ<Edge>();
for (int v = 0; v < g.V; v++)
for (int i = 0; i < g.Deg(v); i++)
pq.Insert(new Edge() { U = v, V = g.AdjV(v, i), W = g.AdjW(v, i) });
DisjointSets ds = new DisjointSets(g.V);
while (pq.Count > 0 && mst.Count < g.V - 1)
{
Edge e = pq.ExtractMin();
int v = e.U;
int w = e.V;
if (ds.FindSet(v) != ds.FindSet(w))
{
ds.Union(v, w);
mst.Add(e);
}
}
}
public IEnumerable<Edge> MST()
{
return mst;
}
}
// -------------------------------------------------------------------------
}
using System;
using System.Collections.Generic;
namespace algorithms.graphs
{
// ----- Tarjan Strongly Connected Components ------------------------------
//
// http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/TarjanSCC.java.html
//
// Depends on:
// -- Graph (algorithms.graphs)
//
// TarjanSCC(Graph g)
// int Count
// int ID(int v)
// bool StronglyConnected(int u, int v)
// static Graph TransitiveReduction(Graph g, out int[] v2v)
// -------------------------------------------------------------------------
public class TarjanSCC
{
public int Count { get; private set; }
bool[] marked;
int[] id;
int[] low;
int pre;
Stack<int> stack;
public TarjanSCC(Graph g)
{
marked = new bool[g.V];
stack = new Stack<int>();
id = new int[g.V];
low = new int[g.V];
for (int v = 0; v < g.V; v++)
{
if (!marked[v]) dfs(g, v);
}
}
void dfs(Graph g, int v)
{
int w;
marked[v] = true;
low[v] = pre++;
int min = low[v];
stack.Push(v);
for (int i = 0; i < g.Deg(v); i++)
{
w = g.AdjV(v, i);
if (!marked[w]) dfs(g, w);
if (low[w] < min) min = low[w];
}
if (min < low[v])
{
low[v] = min;
return;
}
do
{
w = stack.Pop();
id[w] = Count;
low[w] = g.V;
} while (w != v);
Count++;
}
public int ID(int v) { return id[v]; }
public bool StronglyConnected(int u, int v)
{
return id[u] == id[v];
}
}
// -------------------------------------------------------------------------
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using algorithms.math;
namespace algorithms.graphs
{
public static class Transitive
{
// ----- Transitive ----------------------------------------------------
//
// Depends on:
// Bits (algorithms.math)
//
// Graph TransitiveReduction(Graph g, out int[] v2v)
// ---------------------------------------------------------------------
public static Graph TransitiveReduction(Graph g, out int[] v2v)
{
TarjanSCC scc = new TarjanSCC(g);
int[] id2 = new int[g.V];
for (int v = 0; v < g.V; v++)
id2[v] = scc.ID(v);
Array.Sort(id2);
int[] id2v = new int[g.V];
int nd2v = 0;
id2v[id2[0]] = nd2v++;
for (int i = 1; i < g.V; i++)
if (id2[i] != id2[i - 1])
id2v[id2[i]] = nd2v++;
v2v = new int[g.V];
for (int v = 0; v < g.V; v++)
v2v[v] = id2v[scc.ID(v)];
HashSet<long> hse = new HashSet<long>();
for (int v = 0; v < g.V; v++)
{
long vkey = (long)v2v[v] * g.V;
for (int i = 0; i < g.Deg(v); i++)
hse.Add(vkey + v2v[g.AdjV(v, i)]);
}
List<int[]> e = new List<int[]>();
foreach (long vkey in hse)
e.Add(new int[] { (int)(vkey / g.V), (int)(vkey % g.V) });
return new Graph(nd2v, e, true);
}
// topological sort
// backwards Adj -> Bdj
public static int[][] TransitiveClosure(Graph g)
{
int[][] closure = new int[g.V][];
for (int v = 0; v < g.V; v++)
closure[v] = Bits.BitsArray(g.V);
for (int v = 0; v < g.V; v++)
{
Bits.MarkBit(closure[v], v);
for (int i = 0; i < g.Deg(v); i++)
{
int v1 = g.BdjV(v, i);
for (int u = 0; u < g.V; u++)
if (Bits.IsMarked(closure[v], u)) Bits.MarkBit(closure[v1], u);
}
}
}
}
}